from python.mypackage import TreeNode

class Solution(object):
    """
    方法： buildTree
    逻辑: 根据给定的前序遍历和中序遍历数组构造二叉树。
    Args:
        preorder (List[int]): 前序遍历数组。
        inorder (List[int]): 中序遍历数组。
    Returns:
        TreeNode: 构造的二叉树的根节点。
    Time:  
        O(N)其中 N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
    Space:  
        O(n)，递归调用栈的深度最多为 n。
    """
    def buildTree(self, preorder, inorder):

        def recur(root, left, right):
            if left > right: return None;
            node = TreeNode(preorder[root])
            rootindex = dic[preorder[root]]
            node.left = recur(root + 1, left, rootindex - 1)
            node.right = recur(rootindex-left+root + 1, rootindex + 1, right)
            return node
        
        dic, preorder = {}, preorder
        orderlen = len(preorder)
        for i in range(orderlen):
            dic[inorder[i]] = i
        return recur(0, 0 , orderlen-1)
        
    def tree_to_array(self, root):
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            current = queue.pop(0)
            if current:
                result.append(current.val)
                queue.append(current.left)
                queue.append(current.right)
            else:
                result.append(None)
        
        # 去掉末尾的 None 值
        while result and result[-1] is None:
            result.pop()
        
        return result
        
def main():
    solution = Solution()
    
    # 示例 1
    preorder1 = [3, 9, 20, 15, 7]
    inorder1 = [9, 3, 15, 20, 7]
    result1 = solution.buildTree(preorder1, inorder1)
    expected1 = [3, 9, 20, None, None, 15, 7]
    actual1 = solution.tree_to_array(result1)
    print("示例 1:")
    print("输入: preorder =", preorder1, ", inorder =", inorder1)
    print("输出:", actual1)
    print("预期输出:", expected1)
    print("测试通过" if actual1 == expected1 else "测试失败")
    print()

    # 示例 2
    preorder2 = [-1]
    inorder2 = [-1]
    result2 = solution.buildTree(preorder2, inorder2)
    expected2 = [-1]
    actual2 = solution.tree_to_array(result2)
    print("示例 2:")
    print("输入: preorder =", preorder2, ", inorder =", inorder2)
    print("输出:", actual2)
    print("预期输出:", expected2)
    print("测试通过" if actual2 == expected2 else "测试失败")

if __name__ == "__main__":
    main()